package C053;

import C017.main;

// 最大宽度坡
// 给定一个整数数组 A，坡是元组 (i, j)，其中  i < j 且 A[i] <= A[j]
// 这样的坡的宽度为 j - i，找出 A 中的坡的最大宽度，如果不存在，返回 0
// 测试链接 : https://leetcode.cn/problems/maximum-width-ramp/
public class C01 {

	public static void main(String[] args) {
		int[] arr = {9,8,1,0,1,9,4,0,4,1};
		//int[] arr = {6,0,8,2,1,5};
		System.out.println(maxWidthRamp(arr));
	}

	static int MAXLEN = 50001, n, r = 0;
	static int[] arr;

	static int[] stack = new int[MAXLEN];


	public static int maxWidthRamp(int[] nums) {
		arr = nums;
		n = nums.length;
		r = 1;
		for (int i = 0; i < n; i++) {
			if(arr[stack[r - 1]] > arr[i]) {
				stack[r++] = i;
			}
		}

		// 处理结果
		int ans = Integer.MIN_VALUE;
		for (int i = n - 1; i >= 0 ; i--) {
			while(r > 0 && arr[i] >= arr[stack[r - 1]]) {
				//System.out.println(i + " " + stack[r - 1]);
				ans = Math.max(ans, i - stack[--r]);
			}
		}
		return ans;
	}

}
